In a field of pattern recognition, a Hidden Markov model (HMM) as well as a Conditional Random Field and its derived forms have been widely used as a method for recognizing an input signal in which the break of a recognition unit is not clear such as a voice signal and a character string image. The above method can perform determination of the break of a recognition target and recognition of the recognition target at the same time, but requires a long calculation time to match the internal state models with feature vectors. Consequently a new technology capable of accurately and quickly recognizing an input signal in which the break of a recognition unit is not clear has been desired.